First-fit coloring of \P₅,K₄-e\-free graphs

DOI10.1016/J.DAM.2009.12.009MaRDI QIDQ968185zbMATH OpenOpenAlexFDO

Authors T. Karthick, S. A. Choudum

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.12.009

zbMATH Keywords

clique number\(P_{5}\)-free graphson-line coloringfirst-fit coloringpaw-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Effective on-line coloring of \(P_ 5\)-free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• A Note on k-Colorability of P 5-Free Graphs

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Complement reducible graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Effective on-line coloring of \(P_ 5\)-free graphs
• On (\(P_{5}\), diamond)-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line and first fit colorings of graphs
• On-line coloring \(k\)-colorable graphs
• On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
• Paw-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(8)

• \(\mathcal{O}(VE)\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth
• Computational aspects of greedy partitioning of graphs
• -boundedness and related problems on graphs without long induced paths: a survey
• On Computational Aspects of Greedy Partitioning of Graphs
• Vizing bound for the chromatic number on some graph classes
• First-fit coloring of incomparability graphs
• Longest path transversals in claw-free and P₅-free graphs
• On indicated chromatic number of graphs

This page was built for publication: First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs

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