✦ LIBER ✦

Maximum k-colorable subgraphs

✍ Scribed by S. C. Locke

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 303 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060206

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A lower bound is established on the number of edges in a maximum k‐colorable subgraph of a loopless graph G. For the special case of 3‐regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.

📜 SIMILAR VOLUMES

Maximum Δ-edge-colorable subgraphs of cl

Maximum Δ-edge-colorable subgraphs of class II graphs

✍ Vahan V. Mkrtchyan; Eckhard Steffen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

## Abstract A graph __G__ is class II, if its chromatic index is at least Δ + 1. Let __H__ be a maximum Δ‐edge‐colorable subgraph of __G__. The paper proves best possible lower bounds for |__E__(__H__)|/|__E__(__G__)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown tha

On maximum bipartite subgraphs

✍ Günther Malle 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB

## Abstract In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipa

Coloring with three-colored subgraphs

✍ Dhruv Mubayi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

## Abstract Let __f__(__n__) be the minimum number of colors required to color the edges of __K~n,n~__ such that every copy of __K__~3,3~ receives at least three colors on its edges. We prove that $$(0.62+o(1))\sqrt{n}< \, f(n)< \, (1+o(1))\sqrt{n}$$, where the upper bound is obtained by an expli

Vertex partitions and maximum degenerate

Vertex partitions and maximum degenerate subgraphs

✍ Martín Matamala 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract Let __G__ be a graph with maximum degree __d__≥ 3 and ω(__G__)≤ __d__, where ω(__G__) is the __clique number__ of the graph __G__. Let __p__~1~ and __p__~2~ be two positive integers such that __d__ = __p__~1~ + __p__~2~. In this work, we prove that __G__ has a vertex partition __S__~1~,

Maximum number of colorings of (2k, k2)-

Maximum number of colorings of (2k, k2)-graphs

✍ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

Subgraph-avoiding coloring of graphs

✍ Jia Shen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract Given a “forbidden graph” __F__ and an integer __k__, an __F‐avoiding k‐coloring__ of a graph __G__ is a __k__‐coloring of the vertices of __G__ such that no maximal __F__‐free subgraph of __G__ is monochromatic. The __F‐avoiding chromatic number__ __ac__~__F__~(__G__) is the smallest i