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

DOI10.1016/J.DAM.2009.12.009zbMATH Open1225.05094OpenAlexW1503488242MaRDI QIDQ968185FDOQ968185

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

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

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)

Cites Work

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

Cited In (4)

• Computational aspects of greedy partitioning of graphs
• On Computational Aspects of Greedy Partitioning of Graphs
• Vizing bound for the chromatic number on some graph classes
• 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)