Geodesic
P_4-Colorings and P_4-Bipartite Graphs
Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2.

Voir la notice de l'article provenant de la source Episciences

A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4). Examples of P_4-free 2-colorable graphs (also called P_4-bipartite graphs) include parity graphs and graphs with ''few'' P_4s like P_4-reducible and P_4-sparse graphs. We prove that, given k≥ 2, \emphP_4-Free k-Colorability is NP-complete even for comparability graphs, and for P_5-free graphs. We then discuss the recognition, perfection and the Strong Perfect Graph Conjecture (SPGC) for P_4-bipartite graphs with special P_4-structure. In particular, we show that the SPGC is true for P_4-bipartite graphs with one P_3-free color class meeting every P_4 at a midpoint. 
@article{DMTCS_2001_4_2_a4,
     author = {Ho\`ang, Chinh T. and Le, Van Bang},
     title = {P_4-Colorings and {P_4-Bipartite} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {4},
     number = {2},
     year = {2000-2001},
     doi = {10.46298/dmtcs.272},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.272/}
}
TY  - JOUR
AU  - Hoàng, Chinh T.
AU  - Le, Van Bang
TI  - P_4-Colorings and P_4-Bipartite Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2000-2001
VL  - 4
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.272/
DO  - 10.46298/dmtcs.272
LA  - en
ID  - DMTCS_2001_4_2_a4
ER  - 
%0 Journal Article
%A Hoàng, Chinh T.
%A Le, Van Bang
%T P_4-Colorings and P_4-Bipartite Graphs
%J Discrete mathematics & theoretical computer science
%D 2000-2001
%V 4
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.272/
%R 10.46298/dmtcs.272
%G en
%F DMTCS_2001_4_2_a4
Hoàng, Chinh T.; Le, Van Bang. P_4-Colorings and P_4-Bipartite Graphs. Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2. doi : 10.46298/dmtcs.272. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.272/

Cité par Sources :