Questions tagged [forbidden-subgraphs]

For questions related to graphs which do not contain any element of a family of graphs as a subgraph. E.g., Kuratowski characterized *planar graphs* as those which do not have either a subdivision of the complete graph K_5 on five vertices or a subdivision of the complete bipartite graph K_{3,3} as a subgraph.

Filter by
Sorted by
Tagged with
2
votes
0answers
31 views

What is the fewest vertices a non-planar subgraph of the Knight's graph can have?

I was wondering about the title question: What is the fewest vertices a non-planar subgraph of the Knight's graph can have? I have found a subgraph with 14 10 vertices that is non-planar And it ...
1
vote
0answers
17 views

Extremal graphs for paths of fixed length

One can show that if $G$ is a graph on $n$ vertices and does not contain a path (cycles do not count) of length $k$, then $e(G) \leq \frac{k-1}{2}n$ (by induction - remove a vertex of minimal degree ...
1
vote
0answers
16 views

Forbidden $K_4$ in a subgraph of $K_{10}(n)$

In terms of $n\geq 1$, find the maximum possible number of edges in a subgraph $H$ of $K_{10}(n)$, the complete $10$-partite graph with $n$ vertices in each class, containing no copy of $K_4$. It is ...
0
votes
1answer
14 views

Examples to show that the edge-bound for no paths of length $k$ is best

Let $G$ be an $n$-vertex graph containing no path of length $k$. One can show (not that easy but doable) that $e(G) \leq \frac{k-1}{2}n$ (equivalently, the average degree $\bar{d}$ satisfies $\bar{d} \...
10
votes
0answers
95 views

Minecraft water spreading initial arrangements

So as most minecraft players quickly learn, the best way to flood an area is to place water along a diagonal. There are of course other ways to flood the same area with the same number of buckets ...
2
votes
1answer
37 views

Is “induced subgraph” necessary to define an $H$-free graph?

I am looking at what it means for a graph to be $H$-free, if we let $H$ be some arbitrary graph. So far it seems to me that a graph $G$ is $H$-free if it does not contain $H$ as an induced subgraph. ...
3
votes
1answer
91 views

If every $H$-free $2$-connected graph is Hamiltonian then $H$ is $P_3$

I'm stuck with exercise 5 page 72 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory: Show that if being $H$-free implies Hamiltonicity in $2$-connected graphs (where $H$ is ...