## Abstract

Refining a bound by Lih, Wang and Zhu, we prove that if the square G^{2} of a K_{4}-minor-free graph G with maximum degree Δ ≥ 6 does not contain a complete subgraph on ⌊ frac(3, 2) Δ ⌋ + 1 vertices, then G^{2} is ⌊ frac(3, 2) Δ ⌋-colorable.

Original language | English (US) |
---|---|

Pages (from-to) | 6572-6584 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 23-24 |

DOIs | |

State | Published - Dec 6 2009 |

## Keywords

- Brooks-type bound
- Chromatic number
- Series-parallel graph
- Square of a graph
- Vertex coloring

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'A Brooks-type bound for squares of K_{4}-minor-free graphs'. Together they form a unique fingerprint.