Coloring perfect (K_ 4-e)-free graphs

DOI10.1016/0095-8956(87)90048-7MaRDI QIDQ1071025zbMATH OpenOpenAlexFDO

Authors Alan C. Tucker

Publication date 1987

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(87)90048-7

zbMATH Keywords

algorithmcoloringstrong perfect graph conjecture(K4-e)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Recommendations

• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• Publication:4731202
• On Tucker's proof of the strong perfect graph conjecture for \((K_4-e)\)-free graphs
• On the strong perfect graph conjecture
• An algorithm for coloring some perfect graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A characterization of perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs

Cited in

(43)

• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• Counterexamples to three conjectures concerning perfect graphs
• Addendum to: M. Conforti and M. R. Rao, ``Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Discrete Mathematics 104 (1992) 23--47
• On perfectness of sums of graphs
• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• scientific article; zbMATH DE number 4116566 (Why is no real title available?)
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Perfect coloring and linearly χ-boundP6-free graphs
• Strong cliques in diamond-free graphs
• Quasi-star-cutsets and some consequences
• On weakly diamond-free Berge graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Two classes of perfect graphs
• Sequential colorings and perfect graphs
• Finding and counting small induced subgraphs efficiently
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• \(P_4\)-domination in minimal imperfect graphs
• On minimal imperfect graphs without induced P₅
• Even and odd pairs in linegraphs of bipartite graphs
• On Tucker vertices of graphs
• Chair-free Berge graphs are perfect
• On the optimal transversals of the odd cycles
• An algorithm for coloring some perfect graphs
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Colouring diamond-free graphs
• Arboricity, \(h\)-index, and dynamic algorithms
• scientific article; zbMATH DE number 2230322 (Why is no real title available?)
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• Minimax relations for the partial q-colorings of a graph
• Classes of perfect graphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Perfect 2-coloring of the quartic graphs with order at most 8
• Square-free perfect graphs.
• Partial characterizations of circular-arc graphs
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• Building counterexamples
• Finding and counting small induced subgraphs efficiently
• Some properties of minimal imperfect graphs
• Precoloring extension forK₄-minor-free graphs
• The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
• Clique-perfectness and balancedness of some graph classes
• Coloring graphs with no \(\text{odd-}K_4\)

This page was built for publication: Coloring perfect \((K_ 4\)-e)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071025)