✦ LIBER ✦

Linear Chromatic Bounds for a Subfamily of 3K1-free Graphs

✍ Scribed by S. A. Choudum; T. Karthick; M. A. Shalu

Publisher: Springer Japan
Year: 2008
Tongue: English
Weight: 390 KB
Volume: 24
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-008-0801-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Note on Choudum's “chromatic bounds for

Note on Choudum's “chromatic bounds for a class of graphs”

✍ Medha Javdekar 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract If a graph __G__ has no induced subgraph isomorphic to __K__~1,3′~ __K__~5~‐__e__, or a third graph that can be selected from two specific graphs, then the chromatic number of __G__ is either __d__ or __d__ + 1, where __d__ is the maximum order of a clique in __G__.

A general upper bound for the cyclic chr

A general upper bound for the cyclic chromatic number of 3-connected plane graphs

✍ Hikoe Enomoto; Mirko Horňák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB 👁 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number χ~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log

Tight upper bound on the number of edges

Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

✍ Zhi-Zhong Chen; Shiqing Zhang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo

A necessary and sufficient condition for

A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian

✍ Zhou Huai-Lu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 2 views

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1). We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote,

The square of a connected S(K1,3)-free g

The square of a connected S(K1,3)-free graph is vertex pancyclic

✍ George Hendry; Walter Vogler 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

We prove the conjecture of Gould and Jacobson that a connected S(K1,J free graph has a vertex pancyclic square. Since .S(K1,J is not vertex pancyclic, this result is best possible. ## Our notation generally follows that used in [l] . A graph G is Hamilroniun if it contains a cycle through all its